Caches are used to speed up accesses to recently accessed information. During a read from main memory, a copy of the read information will also be stored in the cache. When the processor next accesses the information, the cache will generally supply the information (assuming that the information is still in the cache), instead of having a read performed of main memory to determine the information. This speeds access time to the information, as the memory used in a cache will typically be on the order of ten to hundreds of times faster than the memory used in the main memory of a computer system. With increased speed generally also comes increased cost, area, complexity, and power demands. Consequently caches are highly optimized to work efficiently in the intended computer environment.
Caches are generally organized into two portions, namely a cache data array and a directory. The cache data array stores information from main memory, while the directory contains items such as the main memory addresses to which the information belongs.
A “hit” in the cache occurs when the information being addressed from main memory already exists in the cache. A hit means that the information can be read from the cache and no read is performed to main memory. A “miss” occurs when the information being addressed from main memory is not in the cache. A read is performed to main memory to obtain the information, and a copy of the information is also stored in the cache.
The cache memory generally contains “lines” of information. Each line typically contains information from more than one memory address in main memory. Caches are created this way because it is commonly assumed that if information at one main memory address is used, information at addresses near the original address will also be used. Therefore, lines in the cache contain information from multiple main memory addresses.
Caches generally use some cache line replacement technique to lessen the likelihood that main memory will be accessed. A common cache line replacement technique is called a Least Recently Used (LRU) technique. The LRU cache line replacement technique attempts to determine which line in a cache is the least recently used and to replace the least recently used information with information being read from main memory. The directory typically contains data which is used to determine which lines in the cache are the least recently used.
Although LRU cache line replacement techniques are beneficial in order to update lines in a cache, a need still exists for additional cache line replacement techniques.